Several conventional techniques for encoding two-level facsimile information use the microscopic properties of images by taking advantage of the statistical dependence between neighboring picture elements (pixels). This neighboring pixel dependence can be exploited by coding the connecting pixels that have the same level on a scan line. Another coding technique is to use the statistical dependence between neighboring pixels to predict the pixel levels and then code the resulting error picture. An example of a conventional facsimile coding scheme is the CCITT modified relative element address designate (READ) code described in Hunter and Robinson, "International Digital Facsimile Coding Standards", Proceedings IEEE, Vol. 68, No. 7, pp. 854-867, July 1980. These techniques (and various combinations thereof) significantly reduce the number of bits required to transmit the facsimile information, but additional improvements in efficiency are often desired or required in order to reduce transmission costs.
To increase efficiency, pattern recognition techniques (where the image is viewed as a combination of macroscopic patterns such as characters, lines, or black regions) can be used and the facsimile encoded with codewords to identify image patterns and their respective locations. This approach is generally more efficient than the pixel method because it uses a description which is closer to a perceptual level. Pattern recognition approaches used for coding two-level images are:
(a) Pattern (or image) understanding, in which certain patterns (character and font style) are recognized in accordance with the content of previously processed information; and
(b) Pattern matching, in which new patterns are matched with previously transmitted patterns. In the latter case, if a match exists between the incoming pattern and a previously processed pattern held in storage, the incoming pattern is represented by a code that indicates the matching pattern identity and location in the facsimile being processed. Although the pattern (or image) understanding approach generally yields a higher image compression ratio, aesthetic details of a particular document can be lost. The pattern matching approach has a lower image compression ratio, but maintains more original image quality. It also reduces the risk of error since only slight modifications of pattern shape are allowed. Examples of pattern matching are described in Ascher and Nagy, "A Means for Achieving a High Degree of Compaction on Scan-Digitized Text", IEEE Transactions on Computers, Vol. C-23, pp. 1174-1179, November 1974; and Pratt et al, "Combined Symbol Matching Data Compression System", Proceedings IEEE, Vol. 68, No. 7, pp. 786-796, July 1980.
In various prior art pattern matching systems, symbols such as letters and numbers are matched. However, graphic elements such as line segments and black regions are not matched. In the present invention, a pattern matching technique for facsimile image encoding is described in which both types of patterns can be efficiently processed. In most conventional systems, pattern organization within a library is often inefficient, thereby requiring increased processing time to locate pattern matches. Accordingly, another object of the present invention is to improve the manner in which patterns are stored and accessed. Other objects of the present invention are to improve the manner in which code words are assigned to matching patterns, so that fewer bits are used to represent the transmitted information.